package com.example.arithmeticleetcode.leetcode.y2022;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.TimeZone;
import java.util.concurrent.TimeUnit;

/**
 * @author: ZHEN.FANG@opple.com
 * @create: 2022-08-04 09:33
 * @Description: TODO
 **/
public class AugustDemo {

    /**
     * 1403. 非递增顺序的最小子序列
     *
     * @param nums
     * @return
     */
    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        int sum = Arrays.stream(nums).sum();
        List<Integer> result = new ArrayList<>();
        int tempSum = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (tempSum > sum) {
                break;
            }
            tempSum += nums[i];
            sum -= nums[i];
            result.add(nums[i]);
        }
        return result;
    }

    /**
     * 1450. 在既定时间做作业的学生人数
     *
     * @param startTime
     * @param endTime
     * @param queryTime
     * @return
     */
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int peoples = 0;
        for (int i = 0, len = startTime.length; i < len; i++) {
            if (queryTime < startTime[i] || queryTime > endTime[i]) {
                continue;
            }
            peoples++;
        }
        return peoples;
    }

    /**
     * 1455. 检查单词是否为句中其他单词的前缀
     *
     * @param sentence
     * @param searchWord
     * @return
     */
    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] arr = sentence.split(" ");
        for (int i = 0, len = arr.length; i < len; i++) {
            if (arr[i].startsWith(searchWord)) {
                return i + 1;
            }
        }
        return -1;
    }

    /**
     * 1460. 通过翻转子数组使两个数组相等
     *
     * @param target
     * @param arr
     * @return
     */
    public boolean canBeEqual(int[] target, int[] arr) {
        Map<Integer, Integer> targetMap = new HashMap<>();
        Map<Integer, Integer> arrMap = new HashMap<>();
        for (int num : target) {
            targetMap.put(num, targetMap.getOrDefault(num, 0) + 1);
        }
        for (int num : arr) {
            arrMap.put(num, arrMap.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : targetMap.entrySet()) {
            int value = entry.getValue();
            if (!arrMap.containsKey(entry.getKey()) || arrMap.get(entry.getKey()) != value) {
                return false;
            }
        }
        return true;
    }

    /**
     * 1460. 通过翻转子数组使两个数组相等
     *
     * @param target
     * @param arr
     * @return
     */
    public boolean canBeEqual2(int[] target, int[] arr) {
        Arrays.sort(target);
        Arrays.sort(arr);
        return Arrays.equals(target, arr);
    }

    /**
     * 658. 找到 K 个最接近的元素
     *
     * @param arr
     * @param k
     * @param x
     * @return
     */
    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }
        Collections.sort(list, (a, b) -> {
            if (Math.abs(a - x) != Math.abs(b - x)) {
                return Math.abs(a - x) - Math.abs(b - x);
            } else {
                return a - b;
            }
        });
        List<Integer> result = list.subList(0, k);
        Collections.sort(result);
        return result;
    }

    /**
     * 1464. 数组中两元素的最大乘积
     *
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        Arrays.sort(nums);
        return (nums[0] - 1) * (nums[1] - 1);
    }

    /**
     * 1464. 数组中两元素的最大乘积
     *
     * @param nums
     * @return
     */
    public int maxProduct2(int[] nums) {
        int a = nums[0], b = nums[1];
        if (a < b) {
            int temp = a;
            a = b;
            b = temp;
        }
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] > a) {
                b = a;
                a = nums[i];
            } else if (nums[i] > b) {
                b = nums[i];
            }
        }
        return (a - 1) * (b - 1);
    }

    /**
     * AutoX-1. 网页瀑布流
     *
     * @param num
     * @param block
     * @return
     */
    public static int getLengthOfWaterfallFlow(int num, int[] block) {
        int len = block.length;
        if (num > len) {
            return getMaxHeigh(block, len);
        }
        for (int j = num; j < len; j++) {
            int minHIndex = 0;
            for (int i = 1; i < num; i++) {
                if (block[minHIndex] > block[i]) {
                    minHIndex = i;
                }
            }
            block[minHIndex] += block[j];
        }
        return getMaxHeigh(block, len);

    }

    private static int getMaxHeigh(int[] block, int len) {
        int maxHeigh = block[0];
        for (int i = 1; i < len; i++) {
            if (maxHeigh < block[i]) {
                maxHeigh = block[i];
            }
        }
        return maxHeigh;
    }

    /**
     * AutoX-2. 蚂蚁王国的蜂蜜
     *
     * @param handle
     * @return
     */
    public static double[] honeyQuotes(int[][] handle) {
        int sum = 0;
        int length = 0;
        List<Integer> intList = new ArrayList<>();
        List<Double> list = new ArrayList<>();
        for (int[] ints : handle) {
            System.out.println(Arrays.toString(ints));
            if (ints[0] == 1) {
                sum += ints[1];
                length++;
                intList.add(ints[1]);
            } else if (ints[0] == 2) {
                sum -= ints[1];
                length--;
                Iterator<Integer> iterator = intList.iterator();
                while (iterator.hasNext()) {
                    if (iterator.next() == ints[1]) {
                        iterator.remove();
                        break;
                    }
                }
            } else if (ints[0] == 3) {
                if (sum == 0) {
                    list.add(-1.0);
                    continue;
                }
                list.add((double) sum / length);
            } else {
                if (sum == 0) {
                    list.add(-1.0);
                    continue;
                }
                double d = 0;
                for (Integer num : intList) {

                }
                list.add((double) d / length);
            }
        }
        double[] result = new double[list.size()];
        int i = 0;
        for (Double aDouble : list) {
            result[i++] = aDouble;
        }
        return result;
    }

    /**
     * 6167. 检查相同字母间的距离
     *
     * @param s
     * @param distance
     * @return
     */
    public boolean checkDistances(String s, int[] distance) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0, len = s.length(); i < len; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, i - map.get(c) - 1);
                continue;
            }
            map.put(c, i);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (distance[entry.getKey() - 'a'] != entry.getValue()) {
                return false;
            }
        }
        return true;
    }

    /**
     * 6171. 和相等的子数组
     *
     * @param nums
     * @return
     */
    public boolean findSubarrays(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0, j = 1; j < nums.length; i++, j++) {
            int sum = nums[i] + nums[j];
            if (set.contains(sum)) {
                return true;
            }
            set.add(sum);
        }
        return false;
    }

    /**
     * 2389. 和有限的最长子序列
     *
     * @param nums
     * @param queries
     * @return
     */
    public static int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        int[] result = new int[queries.length];
        for (int j = 0; j < queries.length; j++) {
            if (nums[nums.length - 1] <= queries[j]) {
                result[j] = nums.length;
                continue;
            }
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > queries[j]) {
                    result[j] = i;
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 1592. 重新排列单词间的空格
     *
     * @param text
     * @return
     */
    public String reorderSpaces(String text) {
        int spaceCount = 0;
        int wordCount = 0;
        boolean flag = true;
        for (int i = 0, len = text.length(); i < len; i++) {
            if (text.charAt(i) == ' ') {
                spaceCount++;
                flag = true;
                continue;
            }
            if (flag) {
                flag = false;
                wordCount++;
            }
        }
        System.out.println(spaceCount);
        System.out.println(wordCount);
        StringBuilder sb = new StringBuilder();
        text = text.trim();
        int avgSpaceCount = wordCount == 1 ? 0 : spaceCount / (wordCount - 1);
        int tailSpaceCount = wordCount == 1 ? spaceCount : spaceCount % (wordCount - 1);
        System.out.println(avgSpaceCount);
        System.out.println(tailSpaceCount);
        flag = true;
        for (int i = 0, len = text.length(); i < len; i++) {
            char c = text.charAt(i);
            if (c != ' ') {
                sb.append(c);
                flag = true;
                continue;
            }
            if (flag) {
                for (int j = 0; j < avgSpaceCount; j++) {
                    sb.append(' ');
                }
                flag = false;
            }
        }
        for (int i = 0; i < tailSpaceCount; i++) {
            sb.append(' ');
        }
        return sb.toString();
    }

    /**
     * 667. 优美的排列 II
     *
     * @param n
     * @param k
     * @return
     */
    public int[] constructArray(int n, int k) {
        int idx = 0;
        int[] result = new int[n];
        for (int i = 1, len = n - k; i <= len; i++) {
            result[idx++] = i;
        }
        for (int i = n - k + 1, j = n; i <= j; i++, j--) {
            result[idx++] = j;
            if (i != j) {
                result[idx++] = i;
            }
        }
        return result;
    }

    /**
     * 1598. 文件夹操作日志搜集器
     *
     * @param logs
     * @return
     */
    public int minOperations(String[] logs) {
        int n = 0;
        for (String log : logs) {
            if ("../".equals(log)) {
                n = n > 0 ? --n : n;
                continue;
            }
            if ("./".equals(log)) {
                continue;
            }
            n++;

        }
        return n;
    }

    /**
     * 1619. 删除某些元素后的数组均值
     *
     * @param arr
     * @return
     */
    public double trimMean(int[] arr) {
        Arrays.sort(arr);
        int len = arr.length;
        int avg = (int) (len * 0.1 / 2);
        int sum = 0;
        for (int i = avg, length = len - avg; i < length; i++) {
            sum += arr[i];
        }
        return (double) sum / (len - 2 * avg);

    }


    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, len = nums.length; i < len; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        return null;
    }

    public static boolean isValid(String s) {
        int len = s.length();
        if ((len & 1) == 1) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char tempChar = s.charAt(i);
            if (tempChar == '(' || tempChar == '[' || tempChar == '{') {
                stack.push(tempChar);
                continue;
            }
            if (stack.isEmpty()) {
                return false;
            }
            char pop = stack.pop();
            if (tempChar == ')') {
                if (pop != '(') {
                    return false;
                }
            } else if (tempChar == ']') {
                if (pop != '[') {
                    return false;
                }
            } else {
                if (pop != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty() ? true : false;
    }

    public int[] frequencySort(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        List<Integer> list = new ArrayList<>(nums.length);
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            list.add(num);
        }
        Collections.sort(list, (a, b) -> {
            int aC = map.get(a), bC = map.get(b);
            return aC != bC ? aC - bC : b - a;
        });
        for (int i = 0, len = nums.length; i < len; i++) {
            nums[i] = list.get(i);
        }
        return nums;


    }

    private static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd");


    /**
     * 字符串转成日期类型
     */
    public static void dateFormat() {
        try {
            simpleDateFormat.parse("2021-5-27");
        } catch (ParseException e) {
            e.printStackTrace();
        }
    }

    private static ThreadLocal<SimpleDateFormat> local = new ThreadLocal<SimpleDateFormat>() {
        @Override
        //初始化线程本地变量
        protected SimpleDateFormat initialValue() {
            return new SimpleDateFormat("yyyy-MM-dd");
        }
    };

    /**
     * 字符串转成日期类型
     */
    public static void dateFormat(String s) {
        try {
            //ThreadLocal中的get()方法
            local.get().parse("2021-5-27");
        } catch (ParseException e) {
            e.printStackTrace();
        }
    }

    /**
     * 面试题 01.02. 判定是否互为字符重排
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        int len = s1.length();
        for (int i = 0; i < len; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            map.put(c1, map.getOrDefault(c1, 0) + 1);
            map.put(c2, map.getOrDefault(c2, 0) - 1);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 面试题 17.09. 第 k 个数
     *
     * @param k
     * @return
     */
    public int getKthMagicNumber(int k) {
        int[] factors = {3, 5, 7};
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        set.add(1L);
        heap.offer(1L);
        int magic = 0;
        for (int i = 0; i < k; i++) {
            long curr = heap.poll();
            magic = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (set.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return magic;
    }

    /**
     * 面试题 01.09. 字符串轮转
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s2).contains(s1);
    }

    /**
     * 面试题 01.08. 零矩阵
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        Set<Integer> rowSet = new HashSet<>();
        Set<Integer> colSet = new HashSet<>();
        for (int i = 0, len = matrix.length; i < len; i++) {
            for (int j = 0, len2 = matrix[i].length; j < len2; j++) {
                if (matrix[i][j] == 0) {
                    rowSet.add(i);
                    colSet.add(j);
                }
            }
        }
        for (int i = 0, len = matrix.length; i < len; i++) {
            for (int j = 0, len2 = matrix[i].length; j < len2; j++) {
                if (rowSet.contains(i) || colSet.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }

    }

    /**
     * 1790. 仅执行一次字符串交换能否使两个字符串相等
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean areAlmostEqual(String s1, String s2) {
        int diffCount = 0;
        char s1FirstChar = ' ';
        char s1SecondChar = ' ';
        char s2FirstChar = ' ';
        char s2SecondChar = ' ';
        for (int i = 0, len = s1.length(); i < len; i++) {
            if (s1.charAt(i) == s2.charAt(i)) {
                continue;
            }
            if (diffCount > 2) {
                return false;
            }
            diffCount++;
            if (diffCount == 1) {
                s1FirstChar = s1.charAt(i);
                s2FirstChar = s2.charAt(i);
            }
            if (diffCount == 2) {
                s1SecondChar = s1.charAt(i);
                s2SecondChar = s2.charAt(i);
            }
        }
        return diffCount <= 2 && s1FirstChar == s2SecondChar && s1SecondChar == s2FirstChar;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 817. 链表组件
     *
     * @param head
     * @param nums
     * @return
     */
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        boolean flag = set.contains(head.val);
        int count = 0;
        head = head.next;
        while (head != null) {
            int cur = head.val;
            head = head.next;
            if (flag && set.contains(cur)) {
                continue;
            }
            if (flag) {
                count++;
            }
            flag = set.contains(cur);
        }
        return flag ? ++count : count;
    }

    /**
     * 2432. 处理用时最长的那个任务的员工
     *
     * @param n
     * @param logs
     * @return
     */
    public int hardestWorker(int n, int[][] logs) {
        int id = 0;
        int maxTime = logs[0][1];
        for (int i = 1, len = logs.length; i < len; i++) {
            int curTime = logs[i][1] - logs[i - 1][1];
            if (maxTime < curTime) {
                maxTime = curTime;
                id = logs[i][0];
            } else if (maxTime == curTime && id > logs[i][0]) {
                id = logs[i][0];
            }
        }
        return id;
    }

    /**
     * 1441. 用栈操作构建数组
     *
     * @param target
     * @param n
     * @return
     */
    public static List<String> buildArray(int[] target, int n) {
        List<String> result = new ArrayList<>();
        int index = 0;
        int j = 1;
        while (index < target.length) {
            if (target[index] == j) {
                result.add("Push");
                j++;
            } else {
                while (j++ < target[index]) {
                    result.add("Push");
                    result.add("Pop");
                }
                result.add("Push");
            }
            index++;
        }
        return result;
    }

    /**
     * 1700. 无法吃午餐的学生数量
     *
     * @param students
     * @param sandwiches
     * @return
     */
    public int countStudents(int[] students, int[] sandwiches) {
        int s1 = Arrays.stream(students).sum();
        int s0 = students.length - s1;
        for (int i = 0, len = sandwiches.length; i < len; i++) {
            if (sandwiches[i] == 0 && s0 > 0) {
                s0--;
            } else if (sandwiches[i] == 1 && s1 > 0) {
                s1--;
            } else {
                break;
            }
        }
        return s0 + s1;
    }

    /**
     * 2441. 与对应负数同时存在的最大正整数
     *
     * @param n
     * @param k
     * @return
     */
    public int findMaxK(int[] nums) {
        int result = -1;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        for (Integer num : set) {
            if (num > 0 && set.contains(-num) && num > result) {
                result = num;
            }
        }
        return result;

    }

    /**
     * 2441. 与对应负数同时存在的最大正整数
     *
     * @param n
     * @param k
     * @return
     */
    public int findMaxK2(int[] nums) {
        Arrays.sort(nums);
        int startIndex = 0, endIndex = nums.length - 1;
        while (startIndex < endIndex) {
            if (nums[startIndex] > 0) {
                break;
            }
            if (nums[startIndex] == -nums[endIndex]) {
                return nums[endIndex];
            } else if (nums[startIndex] > -nums[endIndex]) {
                endIndex--;
            } else {
                startIndex++;
            }
        }
        return -1;

    }

    /**
     * 2437. 有效时间的数目
     *
     * @param time
     * @return
     */
    public int countTime(String time) {
        int result = 1;
        int firstChar = time.charAt(0);
        int secondChar = time.charAt(1);
        int thirdChar = time.charAt(3);
        int fourthChar = time.charAt(4);
        if (thirdChar == '?') {
            result *= 6;
        }
        if (fourthChar == '?') {
            result *= 10;
        }
        if (firstChar == '?' && secondChar == '?') {
            result *= 24;
        } else if (firstChar == '?' && secondChar != '?') {
            if (secondChar < '4') {
                result *= 3;
            } else {
                result *= 2;
            }
        } else if (firstChar != '?' && secondChar == '?') {
            if (firstChar < '2') {
                result *= 10;
            } else {
                result *= 4;
            }
        }
        return result;

    }

    /**
     * 2446. 判断两个事件是否存在冲突
     *
     * @param event1
     * @param event2
     * @return
     */
    public boolean haveConflict(String[] event1, String[] event2) {
        return event1[1].hashCode() < event2[0].hashCode() || event2[1].hashCode() < event1[0].hashCode();
    }

    /**
     * 1822. 数组元素积的符号
     *
     * @param nums
     * @return
     */
    public int arraySign(int[] nums) {
        int negativeNumberCount = 0;
        for (int num : nums) {
            if (num == 0) {
                return 0;
            }
            if (num < 0) {
                negativeNumberCount++;
            }
        }
        return negativeNumberCount % 2 == 0 ? 1 : -1;
    }

    /**
     * 1773. 统计匹配检索规则的物品数量
     *
     * @param items
     * @param ruleKey
     * @param ruleValue
     * @return
     */
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int count = 0;
        int index = "type".equals(ruleKey) ? 0 : "color".equals(ruleKey) ? 1 : 2;
        for (List<String> item : items) {
            if (ruleValue.equals(item.get(index))) {
                count++;
            }
        }
        return count;
    }

    /**
     * 6220. 可被三整除的偶数的平均值
     *
     * @param nums
     * @return
     */
    public int averageValue(int[] nums) {
        int sum = 0;
        int count = 0;
        for (int num : nums) {
            if ((num & 1) != 0 || num % 3 != 0) {
                continue;
            }
            sum += num;
            count++;
        }
        return count == 0 ? 0 : sum / count;
    }

    /**
     * 1662. 检查两个字符串数组是否相等
     *
     * @param word1
     * @param word2
     * @return
     */
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for (String s : word1) {
            sb1.append(s);
        }
        for (String s : word2) {
            sb2.append(s);
        }
        return sb1.toString().equals(sb2.toString());
    }

    /**
     * 1668. 最大重复子字符串
     */
    public static int maxRepeating(String sequence, String word) {
        int count = 0;
        int wordIndex = 0;
        int sequenceIndex = 0;
        int len = sequence.length();
        int wordLength = word.length() - 1;
        while (sequenceIndex < len) {
            if (sequence.charAt(sequenceIndex) == word.charAt(wordIndex)) {
                if (wordIndex == wordLength) {
                    wordIndex = 0;
                    count++;
                } else {
                    wordIndex++;
                }
            } else {
                wordIndex = 0;
            }

        }
        return count;
    }

    /**
     * 题目-01. 化学反应
     *
     * @param material
     * @return
     */
    public int lastMaterial(int[] material) {
        return 0;
    }

    /**
     * 2427. 公因子的数目
     *
     * @param a
     * @param b
     * @return
     */
    public int commonFactors(int a, int b) {
        int i = 1;
        int count = 0;
        System.out.println(i);
        while (i <= a && i <= b) {
            if (a % i != 0 || b % i != 0) {
                continue;
            }
            count++;
        }
        return count;
    }

    public String[] sortPeople(String[] names, int[] heights) {
        Map<Integer, String> map = new HashMap<>();
        for (int i = 0, len = names.length; i < len; i++) {
            map.put(heights[i], names[i]);
        }
        Arrays.sort(heights);
        for (int i = 0, len = names.length; i < len; i++) {
            names[i] = map.get(heights[i]);
        }
        return names;
    }

    /**
     * 1684. 统计一致字符串的数目
     *
     * @param allowed
     * @param words
     * @return
     */
    public int countConsistentStrings(String allowed, String[] words) {
        Set<Character> set = new HashSet<>();
        for (int i = 0, len = allowed.length(); i < len; i++) {
            set.add(allowed.charAt(i));
        }
        int count = 0;
        for (String word : words) {
            for (int i = 0, len = word.length(); i < len; i++) {
                if (!set.contains(word.charAt(i))) {
                    break;
                }
                count++;
            }
        }
        return count;
    }

    /**
     * 1704. 判断字符串的两半是否相似
     *
     * @param s
     * @return
     */
    public boolean halvesAreAlike(String s) {
        Set<Character> set = Set.of('A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u');
        int headCount = 0, tailCount = 0;
        int len = s.length(), half = len / 2;
        for (int i = 0; i < len; i++) {
            if (set.contains(s.charAt(i))) {
                if (i < half) {
                    headCount++;
                    continue;
                }
                tailCount++;
            }
        }
        return headCount == tailCount;
    }

    /**
     * 1710. 卡车上的最大单元数
     *
     * @param boxTypes
     * @param truckSize
     * @return
     */
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (o1, o2) -> o2[1] - o1[1]);
        System.out.println(Arrays.toString(boxTypes));
        int result = 0;
        for (int i = 0; i < truckSize; i++) {
            if (truckSize <= 0) {
                break;
            }
            if (boxTypes[i][0] <= truckSize) {
                result += boxTypes[i][0] * boxTypes[i][1];
            } else {
                result += truckSize * boxTypes[i][1];
            }
            truckSize -= boxTypes[i][0];
        }
        return result;
    }

    /**
     * 775. 全局倒置与局部倒置
     *
     * @param nums
     * @return
     */
    public boolean isIdealPermutation(int[] nums) {
        int result = 0;
        for (int i = 0, len = nums.length, len2 = len - 1; i < len; i++) {
            if (i < len2 && nums[i] > nums[i + 1]) {
                result++;
            }
            for (int j = i + 1; j < len; j++) {
                if (nums[i] > nums[j]) {
                    result--;
                }
            }
        }
        return result == 0;
    }

    /**
     * 2469. 温度转换
     *
     * @param celsius
     * @return
     */
    public double[] convertTemperature(double celsius) {
        BigDecimal decimal = new BigDecimal(Double.toString(celsius));
        BigDecimal kelvin = decimal.add(new BigDecimal(Double.toString(273.15))).setScale(5, RoundingMode.HALF_UP);
        BigDecimal fahrenheit = decimal.multiply(new BigDecimal(String.valueOf(1.80)))
                .add(new BigDecimal(Double.toString(32.0))).setScale(5, RoundingMode.HALF_UP);
        return new double[]{kelvin.doubleValue(), fahrenheit.doubleValue()};
    }

    /**
     * 2465. 不同的平均值数目
     *
     * @param nums
     * @return
     */
    public int distinctAverages(int[] nums) {
        Arrays.sort(nums);
        Set<Double> avgSet = new HashSet<>();
        int i = 0, j = nums.length - 1;
        while (i < j) {
            avgSet.add((double) (nums[i] + nums[j]) / 2);
            i++;
            j--;
        }
        return avgSet.size();
    }

    /**
     * 银联-1. 重构链表
     *
     * @param head
     * @return
     */
    public ListNode reContruct(ListNode head) {
        ListNode result = new ListNode(-1);
        ListNode preHead = result;
        while (head != null) {
            if ((head.val & 1) == 1) {
                preHead.next = new ListNode(head.val);
                preHead = preHead.next;
            }

            head = head.next;
        }
        return result.next;
    }

    public int deleteGreatestValue(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            Arrays.sort(grid[i]);
        }
        int result = 0;
        for (int j = 0, colLen = grid.length; j < colLen; j++) {
            int max = 0;
            for (int i = 0, len = grid[0].length; i < len; i++) {
                max = Math.max(max, grid[i][j]);
            }
            result += max;
        }
        return result;
    }

    /**
     * 1945. 字符串转化后的各位数字之和
     *
     * @param s
     * @param k
     * @return
     */
    public int getLucky(String s, int k) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0, len = s.length(); i < len; i++) {
            sb.append(s.charAt(i) - 'a' + 1);
        }
        while (k-- > 0) {
            int len = sb.length();
            if (len < 2) {
                break;
            }
            int result = 0;
            for (int i = 0; i < len; i++) {
                result += sb.charAt(i) - '0';
            }
            System.out.println(result);
            sb.delete(0, len);
            sb.append(result);
        }
        int result = 0;
        for (int i = 0, len = sb.length(); i < len; i++) {
            result += sb.charAt(i) - '0';
        }
        return result;
    }

    /**
     * 1785. 构成特定和需要添加的最少元素
     *
     * @param nums
     * @param limit
     * @param goal
     * @return
     */
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        long diff = Math.abs(goal - sum);
        return (int) ((diff / limit) + (diff % limit == 0 ? 0 : 1));

    }

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(source);
        visited[source] = true;
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            if (vertex == destination) {
                break;
            }
            for (int next : adj[vertex]) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }
        return visited[destination];

    }


    public boolean validPathDFS(int n, int[][] edges, int source, int destination) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        return dfs(source, destination, adj, visited);
    }

    private boolean dfs(int source, int destination, List<Integer>[] adj, boolean[] visited) {
        if (source == destination) {
            return true;
        }
        visited[source] = true;
        for (int cur : adj[source]) {
            if (!visited[cur] && dfs(cur, destination, adj, visited)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 2032. 至少在两个数组中出现的值
     *
     * @param nums1
     * @param nums2
     * @param nums3
     * @return
     */
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        Set<Integer> set1 = getIntegers(nums1);
        Set<Integer> set2 = getIntegers(nums2);
        Set<Integer> set3 = getIntegers(nums3);

        List<Integer> result = new ArrayList<>();
        getMoreOneNum(nums1, set1, set2, set3, result);
        getMoreOneNum(nums2, set1, set2, set3, result);
        getMoreOneNum(nums3, set1, set2, set3, result);
        return null;
    }

    private void getMoreOneNum(int[] nums1, Set<Integer> set1, Set<Integer> set2, Set<Integer> set3, List<Integer> result) {
        for (int i : nums1) {
            int count = 0;
            if (set1.contains(i)) {
                count++;
            }
            if (set2.contains(i)) {
                count++;
            }
            if (set3.contains(i)) {
                count++;
            }
            if (count > 1 && !result.contains(i)) {
                result.add(i);
            }
        }
    }

    private Set<Integer> getIntegers(int[] nums1) {
        Set<Integer> set1 = new HashSet<>();
        for (int i : nums1) {
            if (set1.contains(i)) {
                continue;
            }
            set1.add(i);
        }
        return set1;
    }

    /**
     * 2042. 检查句子中的数字是否递增
     *
     * @param s
     * @return
     */
    public boolean areNumbersAscending(String s) {
        String[] arr = s.split(" ");
        int pre = 0;
        for (String s1 : arr) {
            if (s1.charAt(0) >= 'a') {
                continue;
            }
            int cur = Integer.parseInt(s1);
            if (pre >= cur) {
                return false;
            }
            pre = cur;
        }
        return true;
    }

    /**
     * 2180. 统计各位数字之和为偶数的整数个数
     *
     * @param num
     * @return
     */
    public int countEven(int num) {
        int res = 0;
        for (int i = 1; i <= num; i++) {
            int cur = i, sum = 0;
            while (cur != 0) {
                sum += cur % 10;
                cur /= 10;
            }
            if (sum % 2 == 0) {
                res++;
            }
        }
        return res;
    }

    /**
     * 1807. 替换字符串中的括号内容
     *
     * @param s
     * @param knowledge
     * @return
     */
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> map = new HashMap<>(knowledge.size());
        for (List<String> strings : knowledge) {
            map.put(strings.get(0), strings.get(1));
        }
        int startIndex = 0, endIndex = 0, len = s.length();
        StringBuilder sb = new StringBuilder(len);
        boolean flag = false;
        for (; endIndex < len; endIndex++) {
            char curChar = s.charAt(endIndex);
            if (curChar == '(') {
                startIndex = endIndex + 1;
                flag = true;
                continue;
            } else if (curChar == ')') {
                sb.append(map.getOrDefault(s.substring(startIndex, endIndex), "?"));
                flag = false;
                continue;
            } else {
                if (flag) {
                    continue;
                }
                sb.append(curChar);
            }
        }
        return sb.toString();

    }

    /**
     * 2287. 重排字符形成目标字符串
     *
     * @param s
     * @param target
     * @return
     */
    public int rearrangeCharacters(String s, String target) {
        int[] arr = new int[128];
        for (int i = 0, len = s.length(); i < len; i++) {
            arr[s.charAt(i)]++;
        }
        int[] targetArr = new int[128];
        for (int i = 0, len = target.length(); i < len; i++) {
            targetArr[target.charAt(i)]++;
        }
        int result = Integer.MAX_VALUE;
        for (int i = 96; i < 128; i++) {
            if (targetArr[i] == 0) {
                continue;
            }
            if (arr[i] == 0) {
                return 0;
            }
            result = Math.min(result, arr[i] / targetArr[i]);
        }
        return result;

    }

    /**
     * 2287. 重排字符形成目标字符串
     *
     * @param s
     * @param target
     * @return
     */
    public int rearrangeCharactersMap(String s, String target) {
        Map<Character, Integer> sMap = new HashMap<>(s.length());
        for (int i = 0, len = s.length(); i < len; i++) {
            sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
        }
        Map<Character, Integer> targetMap = new HashMap<>(s.length());
        for (int i = 0, len = target.length(); i < len; i++) {
            targetMap.put(target.charAt(i), targetMap.getOrDefault(target.charAt(i), 0) + 1);
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0, len = target.length(); i < len; i++) {
            char c = target.charAt(i);
            if (sMap.get(c) == 0) {
                return 0;
            }
            result = Math.min(result, sMap.get(c) / targetMap.get(c));
        }
        return result;
    }

    /**
     * 2525. 根据规则将箱子分类
     *
     * @param length
     * @param width
     * @param height
     * @param mass
     * @return
     */
    public String categorizeBox(int length, int width, int height, int mass) {
        int nine = 10_0000_0000;
        boolean volumeFlag = length >= nine || width >= nine || height >= nine
                || length * width * height >= 1_0000;
        System.out.println(length * width * height);
        boolean qualityFlag = mass >= 100;
        if (volumeFlag && qualityFlag) {
            return "Both";
        } else if (volumeFlag) {
            return "Bulky";
        } else if (qualityFlag) {
            return "Heavy";
        }
        return "Neither";

    }

    /**
     * 2293. 极大极小游戏
     *
     * @param nums
     * @return
     */
    public int minMaxGame(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int n = nums.length;
        int left = 0, right = 1, index = 0;
        int newlen = n / 2;
        while (right < n) {
            boolean flag = true;
            while (index < newlen) {
                nums[index++] = flag ? Math.min(nums[left], nums[right]) : Math.max(nums[left], nums[right]);
                left += 2;
                right += 2;
                flag = !flag;
            }
            n = newlen;
            newlen /= 2;
        }
        return nums[0];
    }

    /**
     * 计算一个数值数组的和与位和的差值
     *
     * @param nums
     * @return
     */
    public int differenceOfSum(int[] nums) {
        int sum = 0;
        int numSum = 0;
        for (int num : nums) {
            sum += num;
            while (num > 9) {
                numSum += num % 10;
                num /= 10;
            }
            numSum += num;
        }
        return Math.abs(numSum - sum);
    }


    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        String[] sentence1Arr = sentence1.split(" ");
        String[] sentence2Arr = sentence2.split(" ");
        int i = 0, j = 0;
        while (i < sentence1Arr.length && i < sentence2Arr.length && sentence1Arr[i].equals(sentence2Arr[i])) {
            i++;
        }
        while (j < sentence1Arr.length - i && j < sentence2Arr.length - i
                && sentence1Arr[sentence1Arr.length - j - 1].equals(sentence2Arr[sentence2Arr.length - j - 1])) {
            j++;
        }
        return i + j == Math.min(sentence1Arr.length, sentence2Arr.length);
    }

    /**
     * 1792. 最大平均通过率
     *
     * @param classes
     * @param extraStudents
     * @return
     */
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> {
            double x = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
            double y = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
            return Double.compare(y, x);
        });
        for (int[] aClass : classes) {
            pq.offer(new double[]{aClass[0], aClass[1]});
        }
        while (extraStudents -- > 0) {
            double[] poll = pq.poll();
            System.out.println(Arrays.toString(poll));
            double a = poll[0] + 1, b = poll[1] + 1;
            pq.offer(new double[]{a, b});
        }
        double ans = 0;
        while (!pq.isEmpty()) {
            double[] temp = pq.poll();
            ans += temp[0] / temp[1];
        }
        return ans / classes.length;


    }

    public static void main(String[] args) {
        String numStr = "99.01";
        Double num = Double.parseDouble(numStr);
        System.out.println(num);

    }


}

class Student {

    public void setName() {
        System.setProperty("name", "fz");
    }

    public String getName() {
        return System.getProperty("name");
    }
}

/**
 * 1656. 设计有序流
 */
class OrderedStream {

    private String[] arr;
    private int ptr;


    public OrderedStream(int n) {
        arr = new String[n + 1];
        ptr = 1;
    }

    public List<String> insert(int idKey, String value) {
        List<String> result = new ArrayList<>();
        arr[idKey] = value;
        while (ptr < arr.length && arr[ptr] != null) {
            result.add(arr[ptr++]);
        }
        return result;
    }
}

class Food {
}

class Fruit extends Food {
}

class Apple extends Fruit {
}

class Banana extends Fruit {
}

class GenericTest {
    public void testExtends(List<? extends Fruit> list) {
//报错,extends 为上界通配符,只能取值,不能放.
//因为 Fruit 的子类不只有 Apple 还有 Banana,这里不能确定具体的泛型到底是 Apple 还是 Banana，所以放入任何一种类型都会报错
//list.add(new Apple());
//可以正常获取
        Fruit fruit = list.get(1);
    }

    public void testSuper(List<? super Fruit> list) {
//super 为下界通配符，可以存放元素，但是也只能存放当前类或者子类的实例，以当前的例子来讲，
//无法确定 Fruit 的父类是否只有 Food 一个(Object
        //因此放入 Food 的实例编译不通过
        list.add(new Apple());
// list.add(new Food());
        Object object = list.get(1);
    }
}

/**
 * 901. 股票价格跨度
 */
class StockSpanner {

    private Deque<int[]> stack;

    private int idx;

    public StockSpanner() {
        stack = new ArrayDeque<>();
        stack.push(new int[]{-1, Integer.MAX_VALUE});
        idx = -1;
    }

    public int next(int price) {
        idx++;
        while (price >= stack.peek()[1]) {
            stack.pop();
        }
        int ret = idx - stack.peek()[0];
        stack.push(new int[]{idx, price});
        return ret;
    }
}


class TimeZoneExample {

    public static void main(String[] args) {

        String[] ids = TimeZone.getAvailableIDs();
        for (String id : ids) {

            System.out.println(id + "-----" + TimeZone.getTimeZone(id) + "+++" + displayTimeZone(TimeZone.getTimeZone(id)));
        }

        System.out.println("\nTotal TimeZone ID " + ids.length);

    }

    private static String displayTimeZone(TimeZone tz) {

        long hours = TimeUnit.MILLISECONDS.toHours(tz.getRawOffset());
        long minutes = TimeUnit.MILLISECONDS.toMinutes(tz.getRawOffset())
                - TimeUnit.HOURS.toMinutes(hours);
        // avoid -4:-30 issue
        minutes = Math.abs(minutes);

        String result = "";
        if (hours > 0) {
            result = String.format("(GMT+%d:%02d) %s", hours, minutes, tz.getID());
        } else {
            result = String.format("(GMT%d:%02d) %s", hours, minutes, tz.getID());
        }

        return result;

    }

}